package tk0084.dev.google.quiz;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class DfsPuzzle implements PuzzleStrategy {

	private Puzzle _puzzle;
	private Stack<State> _stack = new Stack<State>();

	private Integer _depthLimit = DEFAULT_DEPTH_LIMIT;
	public static Integer DEFAULT_DEPTH_LIMIT = 10;
	public static Integer MAX_DEPTH_LIMIT = 150;
	public static Integer DEPTH_LIMIT_AMP = 2;

	private Map<Integer, Boolean> _visited = new HashMap<Integer, Boolean>();

	public State unpuzzle(final Puzzle puzzle) {
		_puzzle = puzzle;

		// System.out.println("unpuzzling[dfs]  chars:" +
		// _puzzle.getInitialChars() + " row:" + _puzzle.getRow() + " col:" +
		// _puzzle.getCol());

		State root = State.root(new Table(puzzle.getInitialChars(), puzzle.getRow(), puzzle.getCol()));
		_stack.push(root);

		for (_depthLimit = 1; _depthLimit < MAX_DEPTH_LIMIT; _depthLimit += DEPTH_LIMIT_AMP) {
			 System.out.println("limit:" + _depthLimit);

			doUnpuzzle(root);

			if (_endState != null) {
				return _endState;
			}
			_visited.clear();
		}

//		_depthLimit = 3500;
//		 System.out.println("limit:" + _depthLimit);
//		doUnpuzzle(root);
		
		// while (!_stack.empty()) {
		// // State state = _stack.lastElement();
		// State state = _stack.pop();
		//
		// System.out.println(state.getOrder());
		// if (state.getOrder() == LIMIT) {
		// // _stack.pop();
		// continue;
		// }
		//
		// if (_puzzle.isEndState(state)) {
		// registerEndState(state);
		// // _stack.pop();
		// continue;
		//
		// } else {
		// List<State> nextStates = state.getNextStates();
		// if (nextStates.isEmpty()) {
		// _stack.pop();
		// }
		//
		// for (State next : nextStates) {
		// _stack.push(next);
		// }
		// }
		// }

		return _endState;
	}

	private State _endState;

	private void doUnpuzzle(State state) {

		if (state.getOrder() < _puzzle.getMinOrder()) {
			return;
		}
		
		final int stateHash = String.valueOf(state.getTable().getChars()).hashCode();
		if (Boolean.TRUE.equals(_visited.get(stateHash))) {
			return;
		} else {
			_visited.put(stateHash, Boolean.TRUE);
		}

		if (state.getOrder() == _depthLimit) {
			return;
		}

		if (_puzzle.isEndState(state)) {

			registerEndState(state);

		} else {

			for (State next : state.getNextStates()) {
				doUnpuzzle(next);
			}
		}
	}

	private void registerEndState(State state) {
		if (_endState == null || state.getOrder() < _endState.getOrder()) {
			_endState = state;
			//TODO
			_depthLimit = _endState.getOrder();
		}
	}
}
